/*public class Test {
}*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GraphColoring {
    // 存储所有合法着色方案（每个方案是顶点→颜色的映射，颜色从1开始）
    private List<int[]> result = new ArrayList<>();
    // 图的邻接矩阵（graph[i][j] = 1 表示顶点i和j相邻）
    private int[][] graph;
    // 颜色数量
    private int k;
    // 顶点数
    private int n;

    public List<int[]> solveGraphColoring(int[][] graph, int k) {
        this.graph = graph;
        this.k = k;
        this.n = graph.length;
        // 颜色数组：color[i] 表示顶点i的颜色（初始为0，未分配）
        int[] color = new int[n];
        backtrack(0, color);
        return result;
    }

    /**
     * 回溯函数：逐顶点分配颜色
     * @param vertex 当前要分配颜色的顶点索引
     * @param color 颜色数组
     */
    private void backtrack(int vertex, int[] color) {
        // 终止条件：所有顶点都分配了颜色（找到一个合法方案）
        if (vertex == n) {
            result.add(Arrays.copyOf(color, color.length));
            return;
        }

        // 尝试给当前顶点分配1~k种颜色
        for (int c = 1; c <= k; c++) {
            // 检查颜色c是否合法（与相邻顶点颜色不同）
            if (isValid(vertex, c, color)) {
                // 选择：分配颜色c
                color[vertex] = c;
                // 递归：处理下一个顶点
                backtrack(vertex + 1, color);
                // 回溯：撤销颜色分配（可选，因后续循环会覆盖）
                color[vertex] = 0;
            }
        }
    }

    /**
     * 检查颜色c是否适合当前顶点
     * @param vertex 当前顶点
     * @param c 待分配颜色
     * @param color 颜色数组
     * @return 合法返回true，否则false
     */
    private boolean isValid(int vertex, int c, int[] color) {
        for (int i = 0; i < n; i++) {
            // 若顶点i与当前顶点相邻，且颜色相同，则不合法
            if (graph[vertex][i] == 1 && color[i] == c) {
                return false;
            }
        }
        return true;
    }

    // 测试用例
    public static void main(String[] args) {
        GraphColoring gc = new GraphColoring();
        // 无向图邻接矩阵（4个顶点，构成一个环：0-1-2-3-0）
        int[][] graph = {
                {0, 1, 0, 1},
                {1, 0, 1, 0},
                {0, 1, 0, 1},
                {1, 0, 1, 0}
        };
        int k = 2; // 2种颜色（环图为偶数顶点时，2色可解）
        List<int[]> solutions = gc.solveGraphColoring(graph, k);
        System.out.println("图的" + k + "色着色方案共有 " + solutions.size() + " 种：");
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("方案 " + (i + 1) + "（顶点0~3的颜色）：" + Arrays.toString(solutions.get(i)));
        }
        // 预期输出2种方案：[1,2,1,2] 和 [2,1,2,1]
    }
}
